#pragma once

#include <list>
#include <vector>
#include <string>

using namespace std;

#define MAX_NODE_CHILDREN_NUM 128
class Trie
{
public:
	class TrieNode
	{
	public:
		TrieNode(char c)
		{
			this->c = c;
			memset(children, 0, sizeof(TrieNode*) * MAX_NODE_CHILDREN_NUM);
		}

		char c;
		TrieNode* children[MAX_NODE_CHILDREN_NUM];
	};

	Trie()
	{
		root = NULL;
	}

	bool Build(const vector<string>& data)
	{
		root = new TrieNode(0);
		if (NULL == root)
		{
			return false;
		}

		for (string word : data)
		{
			_AddWord(root, word);
		}

		return true;
	}

	bool Find(string word)
	{
		return _FindWord(root, word);
	}

private:
	void _AddWord(TrieNode* node, string word)
	{
		if (NULL == node || word.empty())
		{
			return;
		}

		char ch = word[0];
		if (NULL == node->children[ch])
		{
			node->children[ch] = new TrieNode(ch);
		}
		_AddWord(node->children[ch], word.substr(1));
	}

	bool _FindWord(TrieNode* node, string word)
	{
		if (word.empty())
		{
			return true;
		}
		if (NULL == node)
		{
			return false;
		}
		char ch = word[0];
		if (NULL == node->children[ch])
		{
			return false;
		}
		return _FindWord(node->children[ch], word.substr(1));
	}

private:
	TrieNode* root;
};



